package com.hackerrank.challenges.redjohnisback;

import java.util.BitSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Solution {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int T = in.nextInt();
		for(int t = 0; t < T; t++) {
			int N = in.nextInt(), wn1 = 1;
			Queue<Integer> w = new LinkedList<Integer>();
			// C is 1st composite number which is 4
			w.add(1); // number of ways for C x 0 wall
			w.add(1); // number of ways for C x 1 wall
			w.add(1); // number of ways for C x 2 wall
			w.add(1); // number of ways for C x 3 wall
			for(int n = 4; n <= N; n++) {
				wn1 += w.poll();
				w.add(wn1);
			}
			int M = wn1, np = 0;
			BitSet c = new BitSet(M + 1);
			for(int p = 2; p <= M; p++) {
				if(!c.get(p))
					np++;
				for(int mp = p + p; mp <= M; mp += p)
					c.set(mp);
			}
			System.out.println(np);
		}
	}
}
